#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

class Solution01 {
public:
    string longestPalindrome(string s) {
        string ret;
        int len = s.size();
        for (int i = 0; i < len; i++) {
            // 两次寻找，一次奇数一次偶数
            int left = i, right = i;
            while (left >= 0 && right < len && s[left] == s[right]) {
                if (right - left + 1 > ret.size())
                    ret = s.substr(left, right - left + 1);
                left--, right++;
            }
            left = i, right = i + 1;
            while (left >= 0 && right < len && s[left] == s[right]) {
                if (right - left + 1 > ret.size())
                    ret = s.substr(left, right - left + 1);
                left--, right++;
            }
        }
        return ret;
    }
};

class Solution02 {
public:
    string addBinary(string a, string b) {
        int enda = a.size() - 1, endb = b.size() - 1;
        int next = 0;
        string ret;
        while (enda >= 0 || endb >= 0) {
            if (enda >= 0) {
                next += a[enda] - '0';
                enda--;
            } 
            if (endb >= 0) {
                next += b[endb] - '0';
                endb--;
            }
            char ch = next % 2 ;
            next /= 2;
            ret += ch + '0';
        }
        if (next) ret += next + '0';
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

// class Solution03 {
// public:
//     void CleanBackZero(string& s) {
//         int end = s.size() - 1;
//         while (end >= 0) {
//             if (s[end--] == '0' && s.size() > 1)
//                 s.pop_back();
//             else
//                 break;
//         }
//     }
//     string multiply(string num1, string num2) {
//         vector<int> tmp;
//         int m = num1.size(), n = num2.size();
//         reverse(num1.begin(), num1.end());
//         reverse(num2.begin(), num2.end());
//         tmp.resize(m + n - 1, 0);
//         int begin = 0;
//         while (begin < n) {
//             int index1 = 0;
//             while (index1 < m) {
//                 int num = (num1[index1] - '0') * (num2[begin] - '0');
//                 tmp[begin + index1] += num;
//                 index1++;
//             }
//             begin++;
//         }
//         string ret;
//         int next = 0;
//         for (int i = 0; i < n + m - 1; i++) {
//             next += tmp[i];
//             ret += next % 10 + '0';
//             next /= 10;
//         }
//         if (next) ret += next % 10 + '0';
//         CleanBackZero(ret);
//         reverse(ret.begin(), ret.end());
//         return ret;
//     }
// };

class Solution03 {
public:
    void CleanBackZero(string& s) {
        int end = s.size() - 1;
        while (end >= 0) {
            if (s[end--] == '0' && s.size() > 1)
                s.pop_back();
            else
                break;
        }
    }

    string multiply(string num1, string num2) {
        // 暴力解法
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        string ret = "0";
        
        int n = num1.size(), m = num2.size();

        int begin = 0;
        while (begin < n) {

            int zeronum = begin;
            string addstr;
            while (zeronum--) addstr += "0";

            int index = 0;
            int next = 0;
            while (index < m) {
                next += (num1[begin] - '0') * (num2[index] - '0');
                addstr += next % 10 + '0';
                next /= 10;
                index++;
            }
            while (next) addstr += next % 10 + '0', next /= 10;

            ret = Addstr(addstr, ret);
            begin++;
        }

        CleanBackZero(ret);
        reverse(ret.begin(), ret.end());
        return ret;
    }

    string Addstr(string a, string b) {
        int enda = a.size() - 1, endb = b.size() - 1;
        int next = 0;
        string ret;
        while (enda >= 0 || endb >= 0) {
            if (enda >= 0) {
                next += a[enda] - '0';
                enda--;
            } 
            if (endb >= 0) {
                next += b[endb] - '0';
                endb--;
            }
            char ch = next % 10;
            next /= 10;
            ret += ch + '0';
        }
        if (next) ret += next + '0';
        reverse(ret.begin(), ret.end());
        return ret;        
    }
};

class Solution04 {
public:
    string removeDuplicates(string s) {
        if (s.empty()) return s;
        // stack<char> st;
        // int len = s.size();
        // // st.push(s[0]);
        // // for (int i = 1; i < len; i++) {
        // //     if (!st.empty() && s[i] != st.top()) 
        // //         st.push(s[i]);
        // //     else st.pop();
        // // }
        // for (auto c : s) {
        //     if (st.empty()) {
        //         st.push(c);
        //     } else {
        //         if (c == st.top()) st.pop();
        //         else st.push(c);
        //     }
        // }
        // string ret;
        // while (!st.empty()) 
        //     ret += st.top(), st.pop();
        // reverse(ret.begin(), ret.end());

        string ret;
        for (auto c : s) {
            if (ret.empty()) ret.push_back(c);
            else {
                if (ret.back() == c) ret.pop_back();
                else ret += c;
            }
        }

        return ret;
    }
};

class Solution05 {
public:
    bool backspaceCompare(string s, string t) {
        string ss, st;
        for (int i = 0; i < s.size(); i++)
            if (!ss.empty() && s[i] == '#')
                ss.pop_back();
            else if (ss.empty() && s[i] == '#')
                continue;
            else
                ss.push_back(s[i]);

        for (int i = 0; i < t.size(); i++)
            if (!st.empty() && t[i] == '#')
                st.pop_back();
            else if (st.empty() && t[i] == '#')
                continue;
            else
                st.push_back(t[i]); 
        cout << ss << " " << st << endl;
        return ss == st;              
    }
};

class Solution06 {
public:
    int calculate(string s) {
        // 若遇到加减直接入栈，若遇到乘除直接计算
        // 遇到空格跳过
        int len = s.size();
        int i = 0;
        stack<int> st;
        char op = '+';
        while (i < len) {
            if (s[i] == ' ') {
                i++;
                continue;
            } else if (s[i] >= '0' && s[i] <= '9') {
                int tmp = 0;
                while (s[i] >= '0' && s[i] <= '9') {
                    tmp = tmp * 10 + (s[i] - '0');
                    i++;
                }

                if (op == '+') st.push(tmp);
                else if (op == '-') st.push(-1 * tmp);
                else if (op == '*') {
                    int num = st.top(); st.pop();
                    num *= tmp;
                    st.push(num);
                } else {
                    int num = st.top(); st.pop();
                    num /= tmp;
                    st.push(num);                    
                }
            } else {
                op = s[i];
                i++;
            }
        }
        int sum = 0;
        while (!st.empty()) {
            sum += st.top();
            st.pop();
        }
        return sum;
    }
};

class Solution07 {
public:
    // string decodeString(string s) {
    //     string ret;
    //     // 只要是字母、数字和 '[' 都将其入栈
    //     stack<char> st;
    //     int i = 0, len = s.size();

    //     while (i < len) {
    //         if (s[i] == ']') {
    //             // 不断的将栈中的数据取出
    //             string addstr;
    //             while (!st.empty() && st.top() != '[') {
    //                 addstr += st.top();
    //                 st.pop();
    //             }

    //             reverse(addstr.begin(), addstr.end());
    //             st.pop();

    //             // int tmp = 0;
    //             // while ()
    //             // int num = st.top() - '0';
    //             // st.pop();

    //             // 现在拿出数据
    //             string nums;
    //             while (!st.empty() && st.top() >= '0' && st.top() <= '9') {
    //                 nums += st.top();
    //                 st.pop();
    //             }
    //             reverse(nums.begin(), nums.end());
    //             int num = stoi(nums);
    //             string add;
    //             while (num--) add += addstr;

    //             for (auto ch : add) st.push(ch);

    //             i++;
    //         } else {

    //             st.push(s[i]);
    //             i++;
    //         }
    //     }

    //     while (!st.empty()) {
            
    //         ret += st.top();
    //         st.pop();
    //     }
    //     reverse(ret.begin(), ret.end());
    //     return ret;
    // }


    string decodeString(string s) {
        stack<string> sts;
        stack<int> sti;
        sts.push("");
        int i = 0, len = s.size();

        while (i < len) {
            if (s[i] >= '0' && s[i] <= '9') {
                int num = 0;
                while (i < len && s[i] >= '0' && s[i] <= '9') {
                    num = num * 10 + s[i] - '0';
                    i++;
                }
                sti.push(num);
            } else if (s[i] == '[') {
                i++;
                string enstr;
                while (i < len && s[i] >= 'a' && s[i] <= 'z') {
                    enstr += s[i];
                    i++;
                }
                sts.push(enstr);
            } else if (s[i] == ']') {
                // 将栈顶的str取出来，然后
                string top = sts.top();
                int num = sti.top();

                sts.pop(), sti.pop();

                string toptop = sts.top();
                sts.pop();
                while (num--) toptop += top;
                sts.push(toptop);
                
                i++;
            } else {
                string enstr;
                while (i < len && s[i] >= 'a' && s[i] <= 'z') {
                    enstr += s[i];
                    i++;
                }
                sts.top() += enstr;                
            }
        }
        // return sts.top();
        string ret = sts.top();
        return ret;
    }
};

int main() {


    return 0;
}

